1. Field of Invention
The present invention generally relates to applications for connection-oriented packet switching networks, and in particular to a method of route selection for alternate paths in connection-oriented networks.
2. Related Art
Routed networks operate by forwarding packets between a source and a destination using intermediate routers which examine the address of a packet and forward the packet to another router until it reaches the destination. Routed networks such as Internet, provide a highly developed addressing structure through which systems can communicate with each other. However, due to routing and queuing delays,in routed networks, and also due to the increasing demand for real-time traffic, to support traffic with widely varying speeds, delay tolerances and connection longevities over a single integrated network becomes a challenging engineering issue.
Connection-oriented networks, e.g. asynchronous transfer mode (ATM) networks, multi-protocol label switched (MPLS) networks, or relay networks, operate by initially establishing a connection between the source and the destination using the physical layer circuit, and then transfer the data without computing overhead, routing and queuing delays associated with the routed networks.
In a connection-oriented packet switching network (or path-oriented routing network), the source to destination path for a packet is determined when a connection is set up, and may or may not be fixed for the duration of the connection. It may not be fixed due to network component failures (links, nodes, etc) requiring the path to be changed to route around the failures. Other mechanisms may also change the path, such as path optimization or path modification.
During path establishment, the requested network resources (bandwidth, memory, CPU, etc) for a particular connection are reserved in advance on links and/or nodes along the selected route in order to ensure that there will be enough of these resources during data transfer. These reservations prevent over utilizations of links and/or nodes. Once links and/or nodes have reached their resources capacities, paths have to be established along different routes. This may lead to using less efficient routes, or bumping of lower priority traffic to accommodate higher priority traffic.
It is through resources reservations that connection-oriented networks eliminate, or at least limit queuing delays associated with the routed networks enabling them to better support traffic with widely varying speeds, delay tolerances and connection longevities over a single integrated network. Through resources reservations connections are guaranteed a requested level of service provided by the connection-oriented network.
As mentioned before, two common mechanisms available in connection-oriented networks for purposes of efficient network resources management and connection management are path optimization and path modification.
Path optimization is a mechanism where a path is rerouted from a less optimal route to a more optimal route. In the spirit of efficient network resources management, optimality may be related to the total amount of network resources that the path is reserving. In such a case, a more optimal route is a route where the total amount of reserved resources is smaller than the amount reserved on the less optimal route.
Path modification is a mechanism where path's attributes such as resources (bandwidth, memory, CPU, etc) requirements are modified, which may result in the path being rerouted, especially in the case when these requirements are increased.
It is known that traffic loss and interruptions associated with the implementation of these two mechanisms may be minimized by utilizing a technique known as “make-before-break” in MPLS and PNNI (private network-network interface) networks. This technique includes the creation of an alternate communications path while the current communications path carries data. Traffic is then switched to the alternate path thus making the alternate path current.
It is to be noted that resources for the alternate communications path must be reserved in advance on all links and/or nodes along its route, while at the same time the current communications path continues to maintain its resources reservations. A potential multiple reservations of resources on links and/or nodes common to both alternate and current communications paths is an unnecessary waste of network resources and may be prevented using the method disclosed in U.S. Pat. No. 5,848,055 issued on Dec. 8, 1998, and assigned to Nortel Networks.
The reason the “make-before-break” method allows a single resources reservations for both alternate and current paths on common links and/or nodes, is that only one of these paths can carry traffic at a particular instance of time, except for a brief period following the traffic switch from the current to the alternate path.
FIG. 1 illustrates a portion of a network having nodes A to F and associated links AB, to FE, each link having a capacity of 1 Mbitts. Suppose a connection requiring 600 Kbits/s is required between nodes A and F. A current communications path of 600 Kbit's between source node A and destination node F is established through links AB, BC, CE and EF, shown in double lines in FIG. 1. The links forming the current communications path are identified in the topology database having 400 Kbit's as available resources. Alternatively, the topology database may indicate that 600 Kbit/s is reserved on these links. The representation of available versus reserved resources does not alter the spirit of the invention, and for the purpose of the example of FIG. 1 the representation of available resources is chosen.
Continuing with the example of FIG. 1, suppose a path optimization mechanism based on “make-before-break” technique is implemented in this network. Suppose that route AC, CE, EF for the connection is more optimal than route AB, BC, CE, EF currently used by the connection's original path. The path optimization mechanism has to learn the more optimal route for an alternate communications path, then needs to establish the alternate path, switch traffic from the current communications path to the alternate path and terminate the original current path and leaving the alternate path as the new current path. The mechanism can only learn the existence of the more optimal route by using the services of a route selection process.
Route selection in connection-oriented networks is typically performed at a source node and through the use of a topology database which contains resources (bandwidth, memory, CPU, etc) information for all links and/or nodes. The information may either indicate the amount of the resources available, or the amount of the reserved resources on such links and/or nodes. Typically, the amount of reserved or available network resources is stored in the topology database in an aggregate form. That is, the total amount of network resources reserved or available is known for all connections, but not on a per connection basis. This ensures topology databases are of a manageable size. The algorithm typically used by route selection process for computing the best route from source to destination is based on Dijkstra shortest-path-first algorithm where links and/or nodes are examined starting at the source (or destination) node and progressing along the best links and/or nodes until the destination (or source) node is reached.
Prior art methods of route selection for an alternate path do not take into consideration the resources reserved for the current communications path. This is limiting because if there is a link and/or node in the network through which :both the current and the alternate communications path need to pass, but there are not enough resources on that link and/or node for both paths, then this link and/or node cannot be selected by the basic method. Suppose, a link of capacity 900 Kbits/s has 100 Kbits/s of unreserved bandwidth, and also carries the current communications path which reserves at least 100 Kbits/s. This link will not be selected by the prior art methods when computing an alternate communications path requiring 200 Kbits/s because this link has only 100 Kbits/s of unreserved bandwidth.
Accordingly, there is a need for a method of route selection for an alternate communications path which makes efficient use of the network resources by taking into account the resources used by the current path.